package com.mars.algorithm;

/**
 * @Author King
 * @create 2020/7/31 9:42
 */
public class Temp {

    public static void main(String[] args) {
        int[] ss = new int[]{78, 45, 13, 90, 56, 34, 65, 67};
//        /mSort(ss);
        // insertSort(ss);
        quickSort(ss, 0, ss.length - 1);
        System.out.println("sdfgd");

        int[] r = new int[]{1, 5, 7, 34, 78, 90, 101, 122, 345};
        int index = tSearch(r, 7);
        if (index == -1) {
            System.out.println("#######不存在查找的元素######");
        } else {
            System.out.println("###查找的元素为:" + r[index]);
        }


        int index2 = dtSearch(r, 0, r.length - 1, 34);
        if (index2 == -1) {
            System.out.println("#######递归不存在查找的元素######");
        } else {
            System.out.println("###递归查找的元素为:" + r[index2]);
        }

    }


    private static void mSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                    flag = true;
                }
                flag = false;
            }
            if (flag) {
                return;
            }
        }
    }

    private static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }


    private static void quickSort(int[] arr, int left, int right) {
        if (null == arr || arr.length <= 1 || left >= right) {
            return;
        }
        int mid = partition(arr, left, right);
        quickSort(arr, left, mid - 1);
        quickSort(arr, mid + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        int key = arr[left];
        while (left < right) {
            while (arr[right] >= key && left < right) {
                right--;
            }
            arr[left] = arr[right];
            while (arr[left] <= key && left < right) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[right] = key;
        return right;
    }


    private static int tSearch(int[] arr, int value) {
        if (null == arr || arr.length == 0) {
            return -1;
        }
        int lo = 0;
        int hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == value) {
                return mid;
            }
            if (arr[mid] < value) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    private static int dtSearch(int[] arr, int lo, int hi, int value) {
        if (lo > hi) {
            return -1;
        }
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == value) {
            return mid;
        }
        if (arr[mid] < value) {
            return dtSearch(arr, mid + 1, hi, value);
        } else {
            return dtSearch(arr, lo, mid - 1, value);
        }
    }


}
